package training;
import java.util.*;
import java.math.*;
// https://www.nowcoder.com/questionTerminal/c0a4b917a15f40a49ca10532ab9019fb
public class Day32_02 {
    // 第一次的思路，超时
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            BigInteger res = fib(a);
            if (res.compareTo(new BigInteger("1000000")) > 0) {
                int num;
                String s = res + "";
                s = s.substring(s.length() - 6, s.length());
                num = Integer.parseInt(s);
                System.out.print(num);
            } else
                System.out.println(res);
        }
    }

    public static BigInteger fib(int n) {
        BigInteger f0 = new BigInteger("1");
        BigInteger f1 = f0;
        BigInteger res = f0;
        while (--n > 0) {
            res = f0.add(f1);
            f0 = f1;
            f1 = res;
        }
        return res;
    }

    private static int[] arr = new int[100001];

    // 通过了的解法
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            System.out.printf(a < 25 ? "%d\n" : "%06d\n", fib2(a));
            //System.out.printf((a<25?"%d\n":"%06d\n"), fib(a));
        }

    }

    public static long fib2(int n) {
        arr[0] = 1;
        arr[1] = 1;
        int res = arr[1];
        if (arr[2] == 0) {
            for (int i = 2; i < 100001; i++) {
                arr[i] = (arr[i - 1] + arr[i - 2]) % 1000000;
            }
        }
        return arr[n];
    }
}